package MonotoneStack.Medium;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

public class LC0739 {
    public int[] dailyTemperatures(int[] temperatures) {
        Deque<Integer> monoStack = new ArrayDeque<>(); // 非递增单调栈；推荐用Deque类代替Stack类，因为Stack是线程安全的，效率低于Deque
        int[] ret = new int[temperatures.length];
        for (int i = 0; i < temperatures.length; i++) {
            while (!monoStack.isEmpty() && temperatures[monoStack.peek()] < temperatures[i]) { // 栈顶元素小于待入栈元素时,栈顶元素出栈
                ret[monoStack.peek()] = i - monoStack.pop();
            }
            // 栈为空或栈顶元素大于等于待入栈元素
            monoStack.push(i);
        }
        // 栈中剩余元素无需处理，因为数组默认值为0

        return ret;
    }
}
